package com.xxd.algo.newcode.mid01.class02;

import java.util.LinkedList;

public class Code01_AllLessNumSubArray {

    public static int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        LinkedList<Integer> qmin = new LinkedList<Integer>();
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int L = 0;
        int R = 0;
        int res = 0;
        while (L < arr.length) {
            while (R < arr.length) {
                // 进 qmax 队列
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                    qmax.pollLast();
                }
                qmax.addLast(R);

                // 进 qmin 队列
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
                    qmin.pollLast();
                }
                qmin.addLast(R);

                // 判断这个范围是否会违规
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break;
                }
                R++;
            }
            // 计算以L开头的 子数组 个数
            res += R - L;

            // 判断是否过期qmin
            if (!qmin.isEmpty() && L == qmin.peekFirst()) {
                qmin.pollFirst();
            }

            // 判断是否过期qmax
            if (!qmax.isEmpty() && L == qmax.peekFirst()) {
                qmax.pollFirst();
            }

            L++;
        }
        return res;
    }

    // for test
    public static int[] getRandomArray(int len) {
        if (len < 0) {
            return null;
        }
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * 10);
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr != null) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        //int[] arr = getRandomArray(30);
        int[] arr = {9, 3, 2, 6, 1, 8, 4, 2, 6};
        int num = 5;
        printArray(arr);
        System.out.println(getNum(arr, num));

    }

}
